On Acyclic Edge-Coloring of Complete Bipartite Graphs

摘要

An acyclic edge-coloring of a graph is a proper edge-coloring withoutbichromatic ($2$-colored) cycles. The acyclic chromatic index of a graph $G$,denoted by $a'(G)$, is the least integer $k$ such that $G$ admits an acyclicedge-coloring using $k$ colors. Let $\Delta = \Delta(G)$ denote the maximumdegree of a vertex in a graph $G$. A complete bipartite graph with $n$ verticeson each side is denoted by $K_{n,n}$. Basavaraju, Chandran and Kummini provedthat $a'(K_{n,n}) \ge n+2 = \Delta + 2$ when $n$ is odd. Basavaraju andChandran provided an acyclic edge-coloring of $K_{p,p}$ using $p+2$ colors andthus establishing $a'(K_{p,p}) = p+2 = \Delta + 2$ when $p$ is an odd prime.The main tool in their approach is perfect $1$-factorization of $K_{p,p}$.Recently, following their approach, Venkateswarlu and Sarkar have shown that$K_{2p-1,2p-1}$ admits an acyclic edge-coloring using $2p+1$ colors whichimplies that $a'(K_{2p-1,2p-1}) = 2p+1 = \Delta + 2$, where $p$ is an oddprime. In this paper, we generalize this approach and present a generalframework to possibly get an acyclic edge-coloring of $K_{n,n}$ which possess aperfect $1$-factorization using $n+2 = \Delta+2$ colors. In this generalframework, we show that $K_{p^2,p^2}$ admits an acyclic edge-coloring using$p^2+2$ colors and thus establishing $a'(K_{p^2,p^2}) = p^2+2 = \Delta + 2$when $p\ge 5$ is an odd prime.